Samochodziki
Limit pamięci: 32 MB
Jasio jest trzylatkiem i bardzo lubi bawić się samochodzikami.
Jasio ma różnych samochodzików.
Wszystkie samochodziki leżą na wysokiej półce, do której Jasio nie
dosięga.
W pokoju jest mało miejsca, więc na podłodze może znajdować się
jednocześnie co najwyżej samochodzików.
Jasio bawi się jednym z samochodzików leżących na podłodze.
Oprócz Jasia w pokoju cały czas przebywa mama.
Gdy Jasio chce się bawić jakimś innym samochodzikiem i jeśli ten
samochodzik jest na podłodze, to sięga po niego.
Jeśli jednak samochodzik znajduje się na półce, to musi mu go podać mama.
Mama podając Jasiowi jeden samochodzik, może przy okazji zabrać
z podłogi dowolnie wybrany przez siebie inny samochodzik i odłożyć go
na półkę (tak, aby na podłodze nie brakło miejsca).
Mama bardzo dobrze zna swoje dziecko i wie dokładnie, którymi
samochodzikami Jasio będzie chciał się bawić.
Dysponując tą wiedzą mama chce zminimalizować liczbę przypadków,
gdy musi podawać Jasiowi samochodzik z półki.
W tym celu musi bardzo rozważnie odkładać samochodziki na półkę.
Zadanie
Napisz program który:
-
wczyta ze standardowego wejścia ciąg kolejnych samochodzików,
którymi będzie chciał się bawić Jasio,
-
obliczy minimalną liczbę przypadków zdejmowania przez mamę
samochodzików z półki,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby
całkowite: , ,
(, ),
pooddzielane pojedynczymi odstępami.
Są to kolejno: łączna liczba samochodzików, liczba
samochodzików mogących jednocześnie znajdować się na podłodze oraz
długość ciągu samochodzików, którymi będzie chciał się bawić
Jasio.
W kolejnych wierszach znajduje się po jednej
liczbie całkowitej.
Są to numery kolejnych samochodzików, którymi będzie chciał się
bawić Jasio (samochodziki są ponumerowane od do ).
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia należy
zapisać jedną liczbę całkowitą - minimalną liczbę przypadków
podania samochodzika z półki przez mamę.
Przykład
Dla danych wejściowych:
3 2 7
1
2
3
1
3
1
2
poprawną odpowiedzią jest:
4
Autor zadania: Krzysztof Sikora.